﻿/**
 * Copyright (c) 2013 Jeremy Wyman
 * Microsoft Public License (Ms-PL)
 * This license governs use of the accompanying software. If you use the software, you accept this license. If you do not accept the license, do not use the software.
 * 1. Definitions
 *    The terms "reproduce", "reproduction", "derivative works", and "distribution" have the same meaning here as under U.S. copyright law.
 *    A "contribution" is the original software, or any additions or changes to the software.
 *    A "contributor" is any person that distributes its contribution under this license.
 *    "Licensed patents" are a contributor's patent claims that read directly on its contribution.
 * 2. Grant of Rights
 *    (A) Copyright Grant - Subject to the terms of this license, including the license conditions and limitations in section 3, each contributor grants you a non-exclusive, worldwide, royalty-free copyright license to reproduce its contribution, prepare derivative works of its contribution, and distribute its contribution or any derivative works that you create.
 *    (B) Patent Grant - Subject to the terms of this license, including the license conditions and limitations in section 3, each contributor grants you a non-exclusive, worldwide, royalty-free license under its licensed patents to make, have made, use, sell, offer for sale, import, and/or otherwise dispose of its contribution in the software or derivative works of the contribution in the software.
 * 3. Conditions and Limitations
 *    (A) No Trademark License - This license does not grant you rights to use any contributors' name, logo, or trademarks.
 *    (B) If you bring a patent claim against any contributor over patents that you claim are infringed by the software, your patent license from such contributor to the software ends automatically.
 *    (C) If you distribute any portion of the software, you must retain all copyright, patent, trademark, and attribution notices that are present in the software.
 *    (D) If you distribute any portion of the software in source code form, you may do so only under this license by including a complete copy of this license with your distribution. If you distribute any portion of the software in compiled or object code form, you may only do so under a license that complies with this license.
 *    (E) The software is licensed "as-is." You bear the risk of using it. The contributors give no express warranties, guarantees or conditions. You may have additional consumer rights under your local laws which this license cannot change. To the extent permitted under your local laws, the contributors exclude the implied warranties of merchantability, fitness for a particular purpose and non-infringement.
 *    
 * More info on: http://tempest.codeplex.com
**/

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

namespace Tempest.Text
{
    internal static partial class TextEngine
    {
        #region Methods
        /// <summary>
        /// 
        /// </summary>
        /// <param name="baseText"></param>
        /// <param name="deltas"></param>
        /// <returns></returns>
        internal static string ApplyDeltas(string baseText, List<Delta> deltas)
        {
            // get the lines of the target file
            List<Line> lines = GetLines(baseText);
            // apply the deltas one at a time, looking for conficts
            int offset = 0;
            for (int i = 0; i < deltas.Count; i++)
            {
                //
                Delta delta = deltas[i];
                if (delta.Lines.Count == 0) 
                    continue;
                switch (delta.Type)
                {
                    case DeltaType.Add:
                        {
                            lines.InsertRange(delta.Begin + offset, delta.Lines);
                            offset += delta.Lines.Count;
                        } break;
                    case DeltaType.Remove:
                        {
                            lines.RemoveRange(delta.Begin + offset, delta.Lines.Count);
                            offset -= delta.Lines.Count;
                        } break;
                }
            }
            // copy the lines into a string buffer
            StringBuilder buffer = new StringBuilder();
            for (int i = 0; i < lines.Count; i++)
            {
                buffer.AppendLine(lines[i].Value);
            }
            // return the resulting string created by collapsing the buffer
            return buffer.ToString();
        }
        /// <summary>
        /// Creates a list of differences between two strings such that right = left + deltas
        /// </summary>
        /// <param name="leftText"></param>
        /// <param name="rightText"></param>
        /// <returns>List of deltas to transform left into right</returns>
        internal static List<Delta> Diff(string leftText, string rightText)
        {
            List<Line> leftLines = GetLines(leftText);
            List<Line> rightLines = GetLines(rightText);
            List<Delta> deltas = new List<Delta>();
            //
            int left = 0;
            int right = 0;
            for (left = 0, right = 0; left < leftLines.Count && right < rightLines.Count; left++, right++)
            {
                int l = 0;
                int r = 0;
                if (leftLines[left] != rightLines[right])
                {
                    bool found = false;
                    for (l = left, r = right + 1; l < leftLines.Count && r < rightLines.Count; r++)
                    {
                        if (leftLines[l] == rightLines[r])
                        {
                            found = true;
                            break;
                        }
                    }
                    if (found)
                    {
                        List<Line> deltaLines = rightLines.GetRange(right, r - right);
                        Delta delta = new Delta()
                        {
                            Begin = left,
                            Type = DeltaType.Add,
                        };
                        delta.Lines.AddRange(deltaLines);
                        deltas.Add(delta);
                        //
                        right = r;
                    }
                    // since it's not new, see how many lines were removed
                    if (!found)
                    {
                        for (l = left + 1, r = right; l < leftLines.Count; l++)
                        {
                            if (leftLines[l] == rightLines[r])
                            {
                                found = true;
                                break;
                            }
                        }
                        if (found)
                        {
                            List<Line> deltaLines = leftLines.GetRange(left, l - left);
                            Delta delta = new Delta()
                            {
                                Begin = left,
                                Type = DeltaType.Remove,
                            };
                            delta.Lines.AddRange(deltaLines);
                            deltas.Add(delta);
                            //
                            left = l;
                        }
                    }
                    //
                    if (!found)
                    {
                        Delta delta = new Delta()
                        {
                            Begin = left,
                            Type = DeltaType.Remove,
                        };
                        delta.Lines.Add(leftLines[left]);
                        deltas.Add(delta);
                        right--;
                    }
                }
            }
            // check to see if there's anything left at the end of the file
            if (left != right)
            {
                if (left > right)
                {
                    deltas.Add(new Delta()
                    {
                        Begin = left,
                        Lines = rightLines.GetRange(right, rightLines.Count - right),
                        Type = DeltaType.Add,
                    });
                }
                else
                {
                    deltas.Add(new Delta()
                    {
                        Begin = left,
                        Lines = leftLines.GetRange(left, leftLines.Count - left),
                        Type = DeltaType.Remove,
                    });
                }
            }
            // return the list of deltas
            return deltas;
        }

        internal static string Integrate(TextBlock headBlock, TextBlock leftBlock, TextBlock rightBlock, out int conflicts)
        {
            conflicts = 0;

            List<Delta> lDeltas = TextEngine.Diff(leftBlock.Text, headBlock.Text);
            List<Delta> rDeltas = TextEngine.Diff(leftBlock.Text, rightBlock.Text);
            List<Line> baseLines = TextEngine.GetLines(headBlock.Text);
            List<MergeConflict> mergeConflicts = new List<MergeConflict>();
            List<Delta> conflicted = new List<Delta>();

            Delta l, r;
            for (int i = 0; i < lDeltas.Count; i++)
            {
                l = lDeltas[i];
                for (int j = 0; j < rDeltas.Count; j++)
                {
                    r = rDeltas[j];
                    if (l.Intersects(r))
                    {
                        if (l != r)
                        {
                            MergeConflict conflict = new MergeConflict()
                            {
                                Left = l,
                                Right = r
                            };
                            conflict.Base = TextEngine.GetString(baseLines.GetRange(conflict.Begin, conflict.Length));
                            mergeConflicts.Add(conflict);
                            conflicted.Add(r);
                        }
                    }
                }
            }

            List<MergeConflict> duplicates = new List<MergeConflict>();

            for (int i = 0; i < mergeConflicts.Count; i++)
            {
                for (int j = i + 1; j < mergeConflicts.Count; j++)
                {
                    if (mergeConflicts[i].Equals(mergeConflicts[j]))
                    {
                        duplicates.Add(mergeConflicts[i]);
                    }
                }
            }

            foreach (MergeConflict duplicate in duplicates)
            {
                mergeConflicts.Remove(duplicate);
            }

            conflicts = mergeConflicts.Count;

            foreach (Delta conflict in conflicted)
            {
                rDeltas.Remove(conflict);
            }

            rDeltas.Sort();
            conflicted.Sort();

            // apply the deltas one at a time, looking for conficts
            int offset = 0;
            for (int i = 0, j = 0; i < rDeltas.Count; )
            {
                int deltaBegin = i < rDeltas.Count ? rDeltas[i].Begin : Int32.MaxValue;
                int conflictBegin = j < mergeConflicts.Count ? mergeConflicts[j].Begin : Int32.MaxValue;

                if (deltaBegin < conflictBegin)
                {
                    Delta delta = rDeltas[i];

                    switch (delta.Type)
                    {
                        case DeltaType.Add:
                            {
                                baseLines.InsertRange(delta.Begin + offset, delta.Lines);
                                offset += delta.Lines.Count;
                            } break;
                        case DeltaType.Remove:
                            {
                                baseLines.RemoveRange(delta.Begin + offset, delta.Lines.Count);
                                offset -= delta.Lines.Count;
                            } break;
                    }
                    i++;
                }
                else
                {
                    MergeConflict conflict = mergeConflicts[j];
                    List<Line> conflictLines = TextEngine.GetLines(conflict.ToString());
                    baseLines.InsertRange(conflict.Begin + offset, conflictLines);
                    offset += conflictLines.Count;
                    j++;
                }
            }

            StringBuilder buffer = new StringBuilder();

            for (int i = 0; i < baseLines.Count; i++)
            {
                buffer.AppendLine(baseLines[i].Value);
            }

            return buffer.ToString();
        }
        /// <summary>
        /// Merges the ends of two branches with a common ancestor into a single value.
        /// </summary>
        /// <param name="baseBlock">The value of the common ancestor</param>
        /// <param name="leftBlock">The value of the left branch</param>
        /// <param name="rightBlock">The value of the right branch</param>
        /// <param name="conflicts">The number of conflicts unresolved</param>
        /// <returns>Merged value of base Δ left + base Δ right</returns>
        internal static string Merge(TextBlock baseBlock, TextBlock leftBlock, TextBlock rightBlock, out int conflicts)
        {
            conflicts = 0;
            // get a list of all of the diff deltas
            List<Delta> deltas = new List<Delta>();
            deltas.AddRange(TextEngine.Diff(baseBlock.Text, leftBlock.Text));
            deltas.AddRange(TextEngine.Diff(baseBlock.Text, rightBlock.Text));
            // look for duplicates and remove them
            List<Delta> duplicates = new List<Delta>();
            for (int i = 0; i < deltas.Count; i++)
            {
                for (int j = i + 1; j < deltas.Count; j++)
                {
                    if (deltas[i] == deltas[j])
                    {
                        duplicates.Add(deltas[j]);
                    }
                }
            }
            foreach (Delta duplicate in duplicates)
            {
                deltas.Remove(duplicate);
            }
            // sort the deltas from the top of the file towards the bottom
            deltas.Sort();
            // get the lines of the target file
            List<Line> lines = GetLines(baseBlock.Text);
            // look for conflicts and pre-resolve them
            List<MergeConflict> mergeConflicts = new List<MergeConflict>();
            for (int i = 0; i < deltas.Count; i++)
            {
                Delta deltaA = deltas[i];
                for (int j = i + 1; j < deltas.Count; j++)
                {
                    Delta deltaB = deltas[j];

                    if ((deltaA.Type == DeltaType.Add || deltaB.Type == DeltaType.Add)
                        && deltaA.Intersects(deltaB))
                    {
                        MergeConflict conflict = new MergeConflict()
                        {
                            Left = deltaA,
                            Right = deltaB,
                        };
                        conflict.Base = TextEngine.GetString(lines.GetRange(conflict.Begin, conflict.Length));
                        mergeConflicts.Add(conflict);
                        // remove the conflicting deltas because they'll be applied as a conflict instead
                        deltas.Remove(deltaA);
                        deltas.Remove(deltaB);
                    }
                }
            }
            // apply the deltas one at a time, looking for conficts
            int offset = 0;
            for (int i = 0; i < deltas.Count; i++)
            {
                Delta delta = deltas[i];
                switch (delta.Type)
                {
                    case DeltaType.Add:
                        {
                            lines.InsertRange(delta.Begin + offset, delta.Lines);
                            offset += delta.Lines.Count;
                        } break;
                    case DeltaType.Remove:
                        {
                            lines.RemoveRange(delta.Begin + offset, delta.Lines.Count);
                            offset -= delta.Lines.Count;
                        } break;
                }
            }
            // write out the conflicts
            for (int i = 0; i < mergeConflicts.Count; i++)
            {
                MergeConflict conflict = mergeConflicts[i];
                // remove the base lines to make room for the conflict markers
                int begin = -1;
                int count = -1;

                if (conflict.Left.Type == DeltaType.Remove)
                {
                    begin = conflict.Left.Begin;
                    count = conflict.Left.Lines.Count;
                }
                else if (conflict.Right.Type == DeltaType.Remove)
                {
                    begin = conflict.Right.Begin;
                    count = conflict.Right.Lines.Count;
                    conflict.Right.Lines = lines.GetRange(begin + offset, count);
                }
                if (begin != -1 && count != -1)
                {
                    lines.RemoveRange(begin + offset, count);
                    offset -= count;
                }
                if (conflict.Base == String.Empty && conflict.Left.Lines.Count == 0 && conflict.Right.Lines.Count == 0)
                    continue;

                lines.Insert(conflict.Begin, new Line(conflict.ToString()));
                offset++;
            }
            // copy the lines into a string buffer
            StringBuilder buffer = new StringBuilder();
            for (int i = 0; i < lines.Count; i++)
            {
                buffer.AppendLine(lines[i].Value);
            }
            // return the resulting string created by collapsing the buffer
            conflicts = mergeConflicts.Count;
            return buffer.ToString();
        }

        private static List<Line> GetLines(string text)
        {
            List<Line> lines = new List<Line>();
            //
            using (StringReader reader = new StringReader(text))
            {
                string line = null;
                while ((line = reader.ReadLine()) != null)
                {
                    lines.Add(new Line(line));
                }
            }
            //
            return lines;
        }

        private static string GetString(List<Line> lines)
        {
            StringBuilder text = new StringBuilder();
            foreach (Line line in lines)
            {
                text.AppendLine(line.Value);
            }
            return text.ToString();
        }
        #endregion
    }
}
